
struct ListNode
{
    int val;
    struct ListNode *next;
 	ListNode(int x) : val(x), next(nullptr) {}
};
class Solution
{
public:
    //逆序链表
    static ListNode* reverseList(ListNode* head)
    {
        ListNode* newhead = new ListNode(0);
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
        }
        cur = newhead->next;
        delete newhead;
        return cur;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2)
    {
        ListNode* n1 = reverseList(head1);
        ListNode* n2 = reverseList(head2);
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        int carry = 0;
        while(n1 || n2 || carry)
        {
            int num1 = n1==nullptr ? 0 : n1->val;
            int num2 = n2==nullptr ? 0 : n2->val;
            int sum = num1 + num2 + carry;
            carry = sum/10;
            prev->next = new ListNode(sum%10);
            prev = prev->next;
            if(n1)
                n1 = n1->next;
            if(n2)
                n2 = n2->next;
        }
        prev = ret->next;
        delete ret;
        return reverseList(prev);
    }
};